In today's data processing, recognition, prediction, and computation tasks are performed using reference databases that characterize input data. Depending on the problem to be solved, these reference databases include patterns that are sub-images, sub-signals, subsets of data and combinations thereof. The patterns stored in the reference databases will be referred to hereinafter as prototypes. As known to practitioners of the art, they are represented generally by a vector, i.e., an array within a space of a given dimension. Well-known methods for characterizing new (unknown) patterns, referred to hereinafter as input patterns, use reference databases that are based on input space mapping algorithms, like K-Nearest-Neighbor (KNN) or Region Of Influence (ROI). The object of the basic principle of these algorithms is to compute the distance (Dist) between the input pattern and each of the stored prototypes in order to find the closest one(s) depending upon predetermined thresholds.
U.S. Pat. No. 5,717,832, of common assignee, describes neural semiconductor chips and artificial neural networks (ANNs) of a new type embedded therein. These ANNs, referred to hereinafter as ZISC ANNs, are based on the input space mapping algorithms referred above and include innovative elementary processors, known as ZISC neurons (ZISC is a registered trade mark of the International Business Machines Corporation). The ZISC neurons are described in U.S. Pat. No. 5,621,863 of common assignee. An essential characteristic of the ZISC neurons resides in their ability to work in parallel, i.e., when an input pattern is provided to ZISC ANN, all the neurons compute simultaneously the distance between the input pattern and each of the prototypes stored therein.
An important aspect of these algorithms is the distance evaluation, referred to as the “norm”, that is used in the distance evaluation process. The selection of this norm is determined, on the one hand, by the problem to be solved, and on the other, by the knowledge required to solve this problem. In a ZISCO36 neuron, the distance Dist between an input pattern V and the prototype P stored therein (each represented by a vector having p components) is calculated by the Manhattan distance (Li norm), i.e., Dist=(|Vk−Pk|)2 or the Maximum distance (Lsup norm), i.e., Dist=max (|Vk−Pk|), wherein Vk and Pk are components of rank k (with k varying from 1 to p) for the input pattern V and the stored prototype P, respectively. In a ZISCO36 neuron, the choice between the Li or Lsup norm is determined by the value of a single bit, the “norm” bit number stored in the neuron. Thus, to evaluate the minimum distance between an input pattern and the memorized prototypes, the pattern is inputted to ZISC ANN, “elementary” distances (Dist) are computed for each component of the input pattern in each neuron, and the distances are determined according to the desired norm. Other norms exist, for instance, the L2 norm, such as Dist=(Vk−Pk))2. The L2 norm is said to be “Euclidean” while the Li and Lsup norms are examples of “non-Euclidean” norms. They all require, however, computing the difference (Vk−Pk) for each component in the elementary distance evaluation. As a matter of fact, the “absolute value of a difference” operator, i.e., |Vk−Pk| is extensively used in the ANN field, although other operators, such as the “match/no match” operator, also written as “match (Vk,Pk)”, are better adapted to specific situations.
The notion of “context” was a novel concept introduced by the ZISC neurons. The context can be advantageously used to differentiate different types of input patterns. For instance, in the field of optical character recognition, the context may be used to distinguish between the upper case and the lower case characters (or to distinguish between different type fonts). In the ZISC neuron, this approach is implemented with a local context Cxt stored in the neuron and a global context CXT held in a common register of the ZISC chip. Consequently, the context approach allows selecting neurons having learned with a determined context and inhibiting all others in ZISC ANN. During the recognition phase, the global context value is compared to the local context value stored in each neuron, and if found identical, the neuron will be selected, otherwise it will be inhibited. As a result, the context allows to configure the ZISC ANN either as a single neural network or as an arrangement of separate groups of neurons wherein all the neurons of a group have the same local context. Regarding the ZISCO36 neuron, the context (local or global) is a value coded on 7 bits. As a result, this context selection mechanism is such that the neurons having a local context different of the global context CXT, are inhibited during the recognition phase to participate to the selection of the closest one(s). However, this selection mechanism has no influence on the distance evaluation process, so that all the neurons will compute the distance between the input pattern and the stored prototypes in accordance with the equations mentioned above.
FIG. 1, consisting of FIGS. 1a and 1b, illustrates the conventional technique of signal (one-dimension space) and image (two-dimension space) analysis when ZISC neurons are used. FIG. 1a shows an electrical signal S (in volts), the amplitude thereof varies as a function of time. Assuming a sliding analysis window that considers seven consecutive sampling points, an input pattern will be represented by a vector having, e.g., seven components, representing the voltage values of seven consecutive sampling points. Consequently, each prototype will also be comprised of seven components. As apparent from FIG. 1a, at time n, vector Un is fully defined as soon as point A has been analyzed. During the recognition phase, when vector Un is inputted to ZISC ANN to be compared to all the prototypes stored in the neurons thereof, all the components of vector Un are broadcasted into the neurons to compute the distances therebetween. Finally, the minimum distance and the category are both determined. Likewise, at time n+1, vector Un+1 is processed in the same manner, the sliding analysis window is shifted by a shift value equal to the sampling point. Note that the sampled signal measured at time n (point A) is fed seven times as a component into ZISC ANN, as it is fed in vectors Un, Un+1, . . . , Un+6, and this may be generalized to any sampling of electrical signals S.
FIG. 1b illustrates a similar example in the field of image processing using the same sliding analysis window. Referring to FIG. 1b, a sub-image I is shown wherein each input pattern is represented by a vector consisting of a block having, e.g., 7 by 7 pixels. In this case, each prototype consists of 49 components. By way of example, at time n, the 49 components of vector Un are fed into ZISC ANN for comparison with the prototypes. Next, at time n+1, the components of vector Un+1 are first fed and, at time n+1+m, the components of vector Un+1+m are fed into ZISC ANN, where m represents the sub-image I width. As a result, each pixel of sub-image I is fed 49 times into ZISC ANN.
ZISC chips are usually packaged in electronic modules that are mounted on a printed circuit board that can be plugged in a Personal Computer (PC) through ISA or PCI buses. Since the computation power of a PC and ZISC ANN is greater than the data transmission rate, the bottleneck of the whole system resides in the communication between the PC (or a host computer) and the ZISC boards whereupon the ZISC chips are mounted. It is thus an important feature to ensure that the data transmission rate fully exploits the parallel processing capabilities of the ZISC technology. Referring to the signal and image analysis/processing illustrated in FIG. 1, the advantages affecting speed are not fully tapped because for each input pattern, each component must be fed several time into the ZISC ANN consuming a significant amount of time.
A likely solution consists to embed memory and microprocessor chips directly on the ZISC board, performing the analysis/processing task on the board itself after transferring the signal S or image I. This solution only displaces the problem without actually solving it. Moreover, even if it can be advantageously used for a stand alone system, it is too complex and expensive for a PC or a host computer.